The decoding of Reed-Solomon error correcting codes requires the calculation of several polynomials with coefficients in a Galois (finite) field. These polynomials are generally known as the Syndrome polynomial, the error evaluator polynomial (.OMEGA.(x) polynomial) and the error locator polynomial (.LAMBDA.(x) polynomial). Prior art designs for computing these polynomials require a separate set of hardware, including storage elements and other circuitry, for computation of each of these polynomials, such as shown in U.S. Pat. No. 4,873,688. In addition, another set of circuitry is required for the evaluation of these polynomials during the actual correction of errors. This can be costly in terms of the required area if the decoder is implemented as part of an integrated circuit. This patent also teaches resolving the .OMEGA.(x) polynomial before calculation of the first derivative of the .LAMBDA.(x) polynomial. While this approach is valid, because the U.S. Pat. No. 4,873,688 fails to teach aligning the storage cells, the resolution is awkward.
Prior art implementations such as U.S. Pat. No. 4,873,688 search for errors in the reverse order to how they are received, which requires the use of some sort of LIFO (last in, first out). Thus, valuable time is lost while reversing the order of the bytes after correction. The U.S. Pat. No. 4,873,688 also teaches a general multiplier using feedback connections for reduction of the byte modulo p(x). These connections tend to slow the circuit down.
For determining the inverse polynomial, prior art designs have used either a shift register implementation as taught in Berlekamp, E. J., Algebraic Coding Theory, McGraw-Hill, 1968, a ROM as taught in U.S. Pat. No. 4,873,688 or a large amount of combinatorial logic for computing the inverse Patel, A. M., "on-the-fly decoder for multiple byte errors," as taught in IBM J. Res. Develop., vol. 30, no. 3, May 1986. Each of these approaches tends to utilize a large amount of surface area on an integrated circuit implementation of such a device.